1104. 二叉树寻路【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 数学

1. 📝 题目描述

• leetcode

在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。

如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；

而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。

给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。

---

示例 1：

输入：label = 14
输出：[1,3,4,14]

示例 2：

输入：label = 26
输出：[1,2,6,10,26]

---

提示：

• 1 <= label <= 10^6

2. 🎯 s.1 - 数学

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number} label
 * @return {number[]}
 */
var pathInZigZagTree = function (label) {
  let level = 1
  while (1 << level <= label) level++
  const res = []
  while (label >= 1) {
    res.push(label)
    // mirror position at current level, then go to parent
    const levelStart = 1 << (level - 1)
    const levelEnd = (1 << level) - 1
    label = Math.floor((levelStart + levelEnd - label) / 2)
    level--
  }
  return res.reverse()
}

• 时间复杂度：$O(\log n)$，其中 $n$ 是 label 的值
• 空间复杂度：$O(\log n)$，结果数组的长度

算法思路：

• 确定 label 所在层级，每层节点范围为 $[2^{k-1},2^k-1]$
• 由于之字形标记，当前节点在本层的镜像位置为 levelStart + levelEnd - label
• 通过镜像位置除以 2 得到父节点，逐层向上回溯到根节点